{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Operations to Sort a Binary Tree by Level"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #逐层排序二叉树所需的最少操作数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>值互不相同</strong> 的二叉树的根节点 <code>root</code> 。</p>\n",
    "\n",
    "<p>在一步操作中，你可以选择 <strong>同一层</strong> 上任意两个节点，交换这两个节点的值。</p>\n",
    "\n",
    "<p>返回每一层按 <strong>严格递增顺序</strong> 排序所需的最少操作数目。</p>\n",
    "\n",
    "<p>节点的 <strong>层数</strong> 是该节点和根节点之间的路径的边数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1 ：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/09/18/image-20220918174006-2.png\" style=\"width: 500px; height: 324px;\">\n",
    "<pre><strong>输入：</strong>root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "- 交换 4 和 3 。第 2 层变为 [3,4] 。\n",
    "- 交换 7 和 5 。第 3 层变为 [5,6,8,7] 。\n",
    "- 交换 8 和 7 。第 3 层变为 [5,6,7,8] 。\n",
    "共计用了 3 步操作，所以返回 3 。\n",
    "可以证明 3 是需要的最少操作数目。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/09/18/image-20220918174026-3.png\" style=\"width: 400px; height: 303px;\">\n",
    "<pre><strong>输入：</strong>root = [1,3,2,7,6,5,4]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：\n",
    "</strong>- 交换 3 和 2 。第 2 层变为 [2,3] 。 \n",
    "- 交换 7 和 4 。第 3 层变为 [4,6,5,7] 。 \n",
    "- 交换 6 和 5 。第 3 层变为 [4,5,6,7] 。\n",
    "共计用了 3 步操作，所以返回 3 。 \n",
    "可以证明 3 是需要的最少操作数目。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3 ：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/09/18/image-20220918174052-4.png\" style=\"width: 400px; height: 274px;\">\n",
    "<pre><strong>输入：</strong>root = [1,2,3,4,5,6]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>每一层已经按递增顺序排序，所以返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 10<sup>5</sup>]</code> 。</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>树中的所有值 <strong>互不相同</strong> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-operations-to-sort-a-binary-tree-by-level](https://leetcode.cn/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-operations-to-sort-a-binary-tree-by-level](https://leetcode.cn/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,3,7,6,8,5,null,null,null,null,9,null,10]', '[1,3,2,7,6,5,4]', '[1,2,3,4,5,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        tmp = list()\n",
    "        q = [root]\n",
    "        ne = list()\n",
    "        res = 0\n",
    "        while q:\n",
    "            ne = list()\n",
    "            for a in q:\n",
    "                if a.left:\n",
    "                    ne.append(a.left)\n",
    "                if a.right:\n",
    "                    ne.append(a.right)\n",
    "            b = {node.val:i for i, node in enumerate(ne)}\n",
    "            c = [node.val for node in ne]\n",
    "            c.sort()\n",
    "            cnt = 0\n",
    "            d = [node.val for node in ne]\n",
    "            n = len(d)\n",
    "            for i in range(n):\n",
    "                if b[c[i]] != i:\n",
    "                    b[d[i]] = b[c[i]]\n",
    "                    d[b[c[i]]], d[i] = d[i], d[b[c[i]]]\n",
    "                    cnt += 1\n",
    "                    \n",
    "            # c = list(range(len(ne)))\n",
    "            # cnt = 0\n",
    "            # for i in range(len(ne)):\n",
    "            #     print(i, b, c)\n",
    "            #     if b[i][1] != c[i]:\n",
    "            #         c[i], c[b[i][1]] = c[b[i][1]], c[i]\n",
    "            #         cnt += 1\n",
    "            #         # print(\"y\", b, c)\n",
    "            res += cnt \n",
    "            # print(b, cnt)\n",
    "            q = ne\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, q = 0, [root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, q = 0, [root]\n",
    "        while q:\n",
    "            a = []      #存放要排序的值\n",
    "            tmp = q\n",
    "            q = []      #存放下一层结点\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "            #循环节计算每一层最少操作数目\n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        a = [root]\n",
    "        while a:\n",
    "            v, b = [], []\n",
    "            for node in a:\n",
    "                v.append(node.val)\n",
    "                if node.left:\n",
    "                    b.append(node.left)\n",
    "                if node.right:\n",
    "                    b.append(node.right)\n",
    "            a = b\n",
    "            n = len(v)\n",
    "            idx = [i for i in range(n)]\n",
    "            idx.sort(key=lambda i: v[i])\n",
    "            for i in range(n):\n",
    "                k = idx[i]\n",
    "                while k != i:\n",
    "                    idx[i] = idx[k]\n",
    "                    idx[k] = k\n",
    "                    k = idx[i]\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        queue = collections.deque([root])\n",
    "\n",
    "        def dp(ls):\n",
    "            tar = ls.copy()\n",
    "            tar.sort()\n",
    "\n",
    "            mp = {n: i for i, n in enumerate(ls)}\n",
    "\n",
    "\n",
    "            ans = 0\n",
    "            for i in range(len(ls)):\n",
    "                if ls[i] == tar[i]:\n",
    "                    continue\n",
    "                else:\n",
    "                    idx = mp[tar[i]]\n",
    "                    ls[i], ls[idx] = ls[idx], ls[i]\n",
    "                    ans += 1\n",
    "\n",
    "                    mp[ls[idx]] = idx\n",
    "                    mp[ls[i]] = i\n",
    "            \n",
    "            return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            tmp = []\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "\n",
    "            ans += dp(tmp)\n",
    "        \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        level = [root]\n",
    "        res = 0\n",
    "        while level:\n",
    "            nodes = [node.val for node in level]\n",
    "            sorted_nodes = sorted(nodes)\n",
    "            dic = {node : i for i, node in enumerate(sorted_nodes)}\n",
    "            for i in range(len(nodes)):\n",
    "                while nodes[dic[nodes[i]]] != nodes[i]:\n",
    "                    nodes[dic[nodes[i]]], nodes[i] = nodes[i], nodes[dic[nodes[i]]]\n",
    "                    res += 1 \n",
    "            level = [kid for node in level for kid in (node.left, node.right) if kid]\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def chaoshi(self, l):\n",
    "        l0, res = sorted(l), 0\n",
    "        for cnt, i in enumerate(l0):\n",
    "            if i!=l[cnt]:\n",
    "                p = l.index(i)\n",
    "                l[cnt], l[p] = i, l[cnt]\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        l, res = [root], 0\n",
    "        while l:\n",
    "            tmp = []\n",
    "            for i in l:\n",
    "                if i.left: tmp.append(i.left)\n",
    "                if i.right: tmp.append(i.right)\n",
    "            res += self.chaoshi([i.val for i in tmp])\n",
    "            l = tmp\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        def getCnt(arr):\n",
    "            sarr = sorted(arr)\n",
    "            d = {}\n",
    "            for i, x in enumerate(arr):\n",
    "                d[x] = i\n",
    "            res = 0\n",
    "            for i in range(len(arr)):\n",
    "                if arr[i] != sarr[i]:\n",
    "                    j = d[sarr[i]]\n",
    "                    arr[i], arr[j] = arr[j], arr[i]\n",
    "                    d[arr[i]]=i\n",
    "                    d[arr[j]]=j\n",
    "                    res += 1\n",
    "            return res\n",
    "        res = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            curlen = len(q)\n",
    "            arr = [node.val for node in q]\n",
    "            res += getCnt(arr)\n",
    "            for node in q[:curlen]:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            q = q[curlen:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, q = 0, [root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        # 方法1: 按层BFS+排序数组+原数组下标字典\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        def getCnt(arr):\n",
    "            # 先得到排序数组\n",
    "            sarr = sorted(arr)\n",
    "            # 然后得到原数组的下标字典\n",
    "            d = {x: i for i, x in enumerate(arr)}\n",
    "            res = 0\n",
    "            for i in range(len(arr)):\n",
    "                if arr[i] != sarr[i]:\n",
    "                    # 当前元素位置不对, 找到正确元素现在的下标, 并交换\n",
    "                    j = d[sarr[i]]\n",
    "                    arr[i], arr[j] = arr[j], arr[i]\n",
    "                    # 同时记得更新下标字典!!!\n",
    "                    d[arr[i]] = i\n",
    "                    d[arr[j]] = j\n",
    "                    # 交换次数+1\n",
    "                    res += 1\n",
    "            return res\n",
    "\n",
    "        res = 0\n",
    "        # 按层BFS部分\n",
    "        q = [root]\n",
    "        while q:\n",
    "            arr = [node.val for node in q]\n",
    "            res += getCnt(arr)\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        def cf(nums):\n",
    "            if not nums: return 0\n",
    "            v = {}\n",
    "            cnt = 0\n",
    "            for x, y in zip(nums, sorted(nums)):\n",
    "                if x != y:\n",
    "                    while x in v:\n",
    "                        x = v[x]\n",
    "                    if x != y:\n",
    "                        cnt += 1\n",
    "                        v[y] = x\n",
    "            return cnt\n",
    "\n",
    "        stack = collections.deque([root])\n",
    "        res = 0\n",
    "        while stack:\n",
    "            n = len(stack)\n",
    "            nval = []\n",
    "            for _ in range(n):\n",
    "                node = stack.popleft()\n",
    "                nval.append(node.val)\n",
    "                if node.left: stack.append(node.left)\n",
    "                if node.right: stack.append(node.right)\n",
    "            res += cf(nval)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        ans = 0\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            rec = []\n",
    "            for i in range(size):\n",
    "                cur = q.popleft()\n",
    "                rec.append(cur.val)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            # 置换环\n",
    "            n = len(rec)\n",
    "            v = sorted(range(n), key=lambda i: rec[i])\n",
    "            vis = [False] * n\n",
    "            ans += n\n",
    "            for i in v:\n",
    "                if vis[i]:\n",
    "                    continue\n",
    "                while not vis[i]:\n",
    "                    vis[i] = True\n",
    "                    i = v[i]\n",
    "                ans -= 1     \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, q = 0, [root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, q = 0, [root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        ans, q = 0, [root]\n",
    "\n",
    "        while q:\n",
    "\n",
    "            a = []\n",
    "\n",
    "            tmp = q\n",
    "\n",
    "            q = []\n",
    "\n",
    "            for node in tmp:\n",
    "\n",
    "                a.append(node.val)\n",
    "\n",
    "                if node.left: q.append(node.left)\n",
    "\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "\n",
    "\n",
    "            n = len(a)\n",
    "\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "\n",
    "\n",
    "\n",
    "            ans += n\n",
    "\n",
    "            vis = [False] * n\n",
    "\n",
    "            for v in a:\n",
    "\n",
    "                if vis[v]: continue\n",
    "\n",
    "                while not vis[v]:\n",
    "\n",
    "                    vis[v] = True\n",
    "\n",
    "                    v = a[v]\n",
    "\n",
    "                ans -= 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        level = [root]\n",
    "        res = 0\n",
    "        while level:\n",
    "            nodes = [node.val for node in level]\n",
    "            sorted_nodes = sorted(nodes)\n",
    "            dic = {node : i for i, node in enumerate(sorted_nodes)}\n",
    "            for i in range(len(nodes)):\n",
    "                while nodes[dic[nodes[i]]] != nodes[i]:\n",
    "                    nodes[dic[nodes[i]]], nodes[i] = nodes[i], nodes[dic[nodes[i]]]\n",
    "                    res += 1 \n",
    "            level = [kid for node in level for kid in (node.left, node.right) if kid]\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, q = 0, [root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        # 方法2: 按层BFS+离散化找环+元素总数减环数\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        def getCnt(arr):\n",
    "            # 通过找环的方式确定最少交换次数\n",
    "            # 每个环的交换次数是环元素个数减1, 所以总共交换次数就是元素总数减环数\n",
    "            # 先得到排序数组\n",
    "            sarr = sorted(arr)\n",
    "            # 然后离散化处理, 进行元素映射\n",
    "            d = {x: i for i, x in enumerate(sarr)}\n",
    "            arr = [d[x] for x in arr]\n",
    "            res = len(arr)\n",
    "            v = set()\n",
    "            for x in arr:\n",
    "                if x not in v:\n",
    "                    # 找到一个新环\n",
    "                    res -= 1\n",
    "                    while x not in v:\n",
    "                        v.add(x)\n",
    "                        x = arr[x]\n",
    "            return res\n",
    "\n",
    "        res = 0\n",
    "        # 按层BFS部分\n",
    "        q = [root]\n",
    "        while q:\n",
    "            arr = [node.val for node in q]\n",
    "            res += getCnt(arr)\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, q = 0, [root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        level = [root]\n",
    "        res = 0\n",
    "        while level:\n",
    "            nodes = [node.val for node in level]\n",
    "            sorted_nodes = sorted(nodes)\n",
    "            dic = {node : i for i, node in enumerate(sorted_nodes)}\n",
    "            for i in range(len(nodes)):\n",
    "                while nodes[dic[nodes[i]]] != nodes[i]:\n",
    "                    nodes[dic[nodes[i]]], nodes[i] = nodes[i], nodes[dic[nodes[i]]]\n",
    "                    res += 1 \n",
    "            level = [kid for node in level for kid in (node.left, node.right) if kid]\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        # 层次遍历得到每一层的节点值\n",
    "        layers = [[]]\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        current_layer_end = root\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            layers[-1].append(node.val)\n",
    "            \n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "                \n",
    "            if node == current_layer_end and queue:\n",
    "                current_layer_end = queue[-1]\n",
    "                layers.append([])\n",
    "        \n",
    "        total_operations = 0\n",
    "        \n",
    "        # 计算每一层变得有序需要多少次操作\n",
    "        for layer in layers:\n",
    "            sorted_layer = sorted(layer)\n",
    "            target_index = {num: idx for idx, num in enumerate(sorted_layer)}\n",
    "            i = 0\n",
    "            \n",
    "            while i < len(layer):\n",
    "                target_location = target_index[layer[i]]\n",
    "                \n",
    "                if target_location == i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    layer[i], layer[target_location] = layer[target_location], layer[i]\n",
    "                    total_operations += 1\n",
    "        \n",
    "        return total_operations\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, q = 0, [root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            vals, cnt = [], 0\n",
    "            for i in range(n):\n",
    "                node = q.popleft()\n",
    "                vals.append(node.val)\n",
    "                cnt += 1\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            vals = sorted(range(cnt), key=lambda i:vals[i])\n",
    "            ans += cnt\n",
    "            vis = [False]*cnt\n",
    "            for v in vals:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = vals[v]\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        ans = 0\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            rec = []\n",
    "            for i in range(size):\n",
    "                cur = q.popleft()\n",
    "                rec.append(cur.val)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            target = sorted(rec)\n",
    "            c = Counter() # 记录目标位置\n",
    "            n = len(rec)\n",
    "            for i in range(n):\n",
    "                c[target[i]] = i\n",
    "            for i in range(n):\n",
    "                while target[i] != rec[i]:\n",
    "                    pos = c[rec[i]]\n",
    "                    rec[i], rec[pos] = rec[pos], rec[i]\n",
    "                    ans += 1      \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        ans = 0\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            rec = []\n",
    "            for i in range(size):\n",
    "                cur = q.popleft()\n",
    "                rec.append(cur.val)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            # 置换环\n",
    "            n = len(rec)\n",
    "            target = sorted(rec)\n",
    "            mp = defaultdict()\n",
    "            for i, j in enumerate(target):\n",
    "                mp[j] = i\n",
    "            vis = [False] * n\n",
    "            loop = 0\n",
    "            for i in range(n):\n",
    "                if vis[i]:\n",
    "                    continue\n",
    "                while not vis[i]:\n",
    "                    vis[i] = True\n",
    "                    i = mp[rec[i]]\n",
    "                loop += 1\n",
    "            ans += n - loop        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        # 直接想法：记录下每一层的元素\n",
    "        # 将一个无序的数组变为有序数组需要的最少操作步数？\n",
    "        # 交换排序的最少操作步数\n",
    "        # 逆序数\n",
    "        data = []\n",
    "        que = collections.deque()\n",
    "        if root is None:\n",
    "            return 0\n",
    "        que.append(root)\n",
    "        last = root\n",
    "        first = root\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            if first == cur:\n",
    "                data.append([])\n",
    "\n",
    "            data[-1].append(cur.val)\n",
    "\n",
    "            if cur.left:\n",
    "                que.append(cur.left)\n",
    "            if cur.right:\n",
    "                que.append(cur.right)\n",
    "\n",
    "            if last == cur:\n",
    "                first = que[0] if que else None\n",
    "                last = que[-1] if que else None\n",
    "        ans = 0\n",
    "\n",
    "        for layer in data:\n",
    "            sorted_layer = sorted(layer)\n",
    "            idx = 0\n",
    "            while idx < len(layer):\n",
    "                if sorted_layer[idx] != layer[idx]:\n",
    "                    ans += 1\n",
    "                    target_idx = bisect.bisect_left(sorted_layer, layer[idx])\n",
    "                    layer[idx], layer[target_idx] = layer[target_idx], layer[idx]\n",
    "                else:\n",
    "                    idx += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        def f(nums):\n",
    "            if not nums: return 0\n",
    "            v = {}\n",
    "            cnt = 0\n",
    "            for x, y in zip(nums, sorted(nums)):\n",
    "                if x != y:\n",
    "                    while x in v:\n",
    "                        x = v[x]\n",
    "                    if x != y:\n",
    "                        cnt += 1\n",
    "                        v[y] = x\n",
    "            return cnt\n",
    "\n",
    "        q = deque([root])\n",
    "        ans = 0\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            nums = []\n",
    "            for _ in range(n):\n",
    "                x = q.popleft()\n",
    "                if not x: continue\n",
    "                nums.append(x.val)\n",
    "                q.append(x.left)\n",
    "                q.append(x.right)\n",
    "            ans += f(nums)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            \n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda x: a[x])\n",
    "\n",
    "            ans += n\n",
    "            seen = [False] * n\n",
    "            for v in a:\n",
    "                if seen[v]:\n",
    "                    continue\n",
    "                while not seen[v]:\n",
    "                    seen[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            a = []\n",
    "            sz = len(q)\n",
    "            for i in range(sz):\n",
    "                node = q.popleft()\n",
    "                a.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            # 离散化\n",
    "            b = sorted(a)\n",
    "            a = [bisect_left(b, v) for v in a]\n",
    "            n = len(a)\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n",
    "                    \n",
    "                \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        queue = collections.deque([root])\n",
    "\n",
    "        # 置换环\n",
    "        def dp(ls):\n",
    "            cp = sorted(ls.copy())\n",
    "            mp = {nn:i for i, nn in enumerate(cp)}\n",
    "\n",
    "            res = []\n",
    "            for l in ls:\n",
    "                res.append(mp[l])\n",
    "            \n",
    "\n",
    "            vis = [False] * len(ls)\n",
    "            ans = 0\n",
    "            for i in range(len(res)):\n",
    "                idx = res[i]\n",
    "                if not vis[idx]:\n",
    "                    cnt = 0\n",
    "                    while not vis[idx]:\n",
    "                        vis[idx] = True\n",
    "                        idx = res[idx]\n",
    "                        cnt += 1\n",
    "                    ans += cnt - 1\n",
    "            \n",
    "            return ans\n",
    "                \n",
    "\n",
    "\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            tmp = []\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "\n",
    "            ans += dp(tmp)\n",
    "        \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        queue = collections.deque([root])\n",
    "\n",
    "        # 置换环\n",
    "        def dp(ls):\n",
    "            # cp = sorted(ls.copy())\n",
    "            # mp = {nn:i for i, nn in enumerate(cp)}\n",
    "\n",
    "            # res = []\n",
    "            # for l in ls:\n",
    "            #     res.append(mp[l])\n",
    "            n = len(ls)\n",
    "            res = sorted(range(n), key=lambda i: ls[i])\n",
    "            \n",
    "\n",
    "            vis = [False] * len(ls)\n",
    "            ans = 0\n",
    "            for i in range(len(res)):\n",
    "                idx = res[i]\n",
    "                if not vis[idx]:\n",
    "                    cnt = 0\n",
    "                    while not vis[idx]:\n",
    "                        vis[idx] = True\n",
    "                        idx = res[idx]\n",
    "                        cnt += 1\n",
    "                    ans += cnt - 1\n",
    "            \n",
    "            return ans\n",
    "                \n",
    "\n",
    "\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            tmp = []\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "\n",
    "            ans += dp(tmp)\n",
    "        \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        res=0\n",
    "        q=[root]\n",
    "        while q:\n",
    "            a=[]\n",
    "            size=len(q)\n",
    "            for _ in range(size):\n",
    "                t=q.pop(0)\n",
    "                a.append(t.val)\n",
    "                if t.left:\n",
    "                    q.append(t.left)\n",
    "                if t.right:\n",
    "                    q.append(t.right)\n",
    "            n=len(a)\n",
    "            a=sorted(range(n), key=lambda i:a[i])\n",
    "            \n",
    "            res+=n\n",
    "            vis=[0]*n\n",
    "            for v in a:\n",
    "                if vis[v]==1:\n",
    "                    continue\n",
    "                while vis[v]==0:\n",
    "                    vis[v]=1\n",
    "                    v=a[v]\n",
    "                res-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        def check():\n",
    "            nonlocal ans\n",
    "            ind = {num: i for i, num in enumerate(cur)}\n",
    "    \n",
    "            lst = sorted(cur)\n",
    "            m = len(lst)\n",
    "            uf = UnionFind(m)\n",
    "            for i in range(m):\n",
    "                uf.union(ind[lst[i]], ind[cur[i]])\n",
    "            group = uf.get_root_size()\n",
    "            for p in group:\n",
    "                ans += group[p] - 1\n",
    "            return \n",
    "        \n",
    "        ans = 0\n",
    "        stack = [root] if root else []\n",
    "        while stack:\n",
    "            nex = []\n",
    "            cur = [node.val for node in stack]\n",
    "            check()\n",
    "            for node in stack:\n",
    "                if node.left:\n",
    "                    nex.append(node.left)\n",
    "                if node.right:\n",
    "                    nex.append(node.right)\n",
    "            stack = nex[:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        q=deque([root])\n",
    "        ans=0\n",
    "        while q:\n",
    "            s=len(q)\n",
    "            for i in range(s):\n",
    "                r=q.popleft()\n",
    "                if r.left:\n",
    "                    q.append(r.left)\n",
    "                if r.right:\n",
    "                    q.append(r.right)\n",
    "            j=sorted(range(len(q)),key=lambda x:q[x].val)\n",
    "            for i in range(len(j)):\n",
    "                while i!=j[i]:\n",
    "                    a,b=j[i],j[j[i]]\n",
    "                    j[i],j[a]=b,a\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        # def switch_time1(nums):\n",
    "        #     ans = 0\n",
    "        #     locs = {}\n",
    "        #     n = len(nums)\n",
    "        #     for i,num in enumerate(nums):\n",
    "        #         locs[num] = i\n",
    "        #     sorted_nums = sorted(nums)\n",
    "        #     for i in range(n):\n",
    "        #         if nums[i] != sorted_nums[i]:\n",
    "        #             loc = locs[sorted_nums[i]]\n",
    "        #             ans += 1\n",
    "        #             locs[nums[i]] = loc\n",
    "        #             locs[sorted_nums[i]] = i\n",
    "        #             nums[i], nums[loc] = nums[loc], nums[i]\n",
    "        #     return ans\n",
    "        def switch_time(nums):\n",
    "            n = len(nums)\n",
    "            sorted_idx = sorted(range(n), key=lambda i:nums[i])\n",
    "            visited = [False] * n\n",
    "            ans = n\n",
    "            for i in range(n):\n",
    "                if not visited[i]:\n",
    "                    nxt = i\n",
    "                    while not visited[nxt]:\n",
    "                        visited[nxt] = True\n",
    "                        nxt = sorted_idx[nxt]\n",
    "                    ans -= 1\n",
    "            return ans\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            nums = []\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                nums.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            ans += switch_time(nums)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        # 层次遍历得到每一层的节点值，计算每一层变得有序需要多少次操作\n",
    "        # 每一层变得有序的最少操作次数：从第一个数开始：如果该数在它的目标位置上调到下一个元素，否则将该元素与目标为之上的元素交换\n",
    "        if root is None: return 0\n",
    "        data = [[]]\n",
    "        que = collections.deque()\n",
    "        que.append(root)\n",
    "        tail = root\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            data[-1].append(cur.val)\n",
    "            if cur == tail:\n",
    "                data.append([])\n",
    "                \n",
    "            if cur.left:\n",
    "                que.append(cur.left)\n",
    "            if cur.right:\n",
    "                que.append(cur.right)\n",
    "            if tail == cur and que:\n",
    "                tail = que[-1]\n",
    "\n",
    "        ans = 0\n",
    "        for layer in data:\n",
    "            sorted_layer = sorted(layer)\n",
    "            target_index = {num: idx for idx, num in enumerate(sorted_layer)}\n",
    "            i = 0\n",
    "            while i < len(layer):\n",
    "                loc = target_index[layer[i]]\n",
    "                if loc == i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    layer[i], layer[loc] = layer[loc], layer[i]\n",
    "                    ans += 1\n",
    "        return ans\n",
    "                \n",
    "\n",
    "        return 0\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self, n):\n",
    "        self.parents = {}\n",
    "        self.union_cnt = n\n",
    "    def find(self,x):\n",
    "        if(x != self.parents[x]):\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "    def union(self,x,y):\n",
    "        ax = self.find(x)\n",
    "        ay = self.find(y)\n",
    "        if(ax == ay):\n",
    "            return True\n",
    "        self.parents[ax] = ay\n",
    "        self.union_cnt -= 1\n",
    "        return False\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        que = deque()\n",
    "        que.append([root,1])\n",
    "        predepth = 0\n",
    "        def calcTimes(nums):\n",
    "            n = len(nums)\n",
    "            if(n <= 1):\n",
    "                return 0  \n",
    "            numsSort = sorted(nums)\n",
    "            us = UnionSet(n)\n",
    "            for num in nums:\n",
    "                us.parents[num] = num\n",
    "            for n1, n2 in zip(nums, numsSort):\n",
    "                us.union(n1,n2)\n",
    "            return n - us.union_cnt\n",
    "        result = 0\n",
    "        tmp = []\n",
    "        while(que):\n",
    "            node, depth = que.popleft()\n",
    "            if(depth > predepth):\n",
    "                result += calcTimes(tmp)\n",
    "                tmp = [node.val]\n",
    "                predepth = depth\n",
    "            else:\n",
    "                tmp.append(node.val)\n",
    "            if(node.left):\n",
    "                que.append([node.left, depth+1])\n",
    "            if(node.right):\n",
    "                que.append([node.right, depth+1])\n",
    "        result += calcTimes(tmp)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        def switch_time(nums):\n",
    "            ans = 0\n",
    "            locs = {}\n",
    "            n = len(nums)\n",
    "            for i,num in enumerate(nums):\n",
    "                locs[num] = i\n",
    "            sorted_nums = sorted(nums)\n",
    "            for i in range(n):\n",
    "                if nums[i] != sorted_nums[i]:\n",
    "                    loc = locs[sorted_nums[i]]\n",
    "                    ans += 1\n",
    "                    locs[nums[i]] = loc\n",
    "                    locs[sorted_nums[i]] = i\n",
    "                    nums[i], nums[loc] = nums[loc], nums[i]\n",
    "            return ans\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            nums = []\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                nums.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            ans += switch_time(nums)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self, n):\n",
    "        self.parents = {}\n",
    "        self.union_cnt = n\n",
    "    def find(self,x):\n",
    "        if(x != self.parents[x]):\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "    def union(self,x,y):\n",
    "        ax = self.find(x)\n",
    "        ay = self.find(y)\n",
    "        if(ax == ay):\n",
    "            return True\n",
    "        self.parents[ax] = ay\n",
    "        self.union_cnt -= 1\n",
    "        return False\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        que = deque()\n",
    "        que.append([root,1])\n",
    "        predepth = 0\n",
    "        def calcTimes(nums):\n",
    "            n = len(nums)\n",
    "            if(n <= 1):\n",
    "                return 0  \n",
    "            numsSort = sorted(nums)\n",
    "            us = UnionSet(n)\n",
    "            for num in nums:\n",
    "                us.parents[num] = num\n",
    "            for n1, n2 in zip(nums, numsSort):\n",
    "                us.union(n1,n2)\n",
    "            return n - us.union_cnt\n",
    "        result = 0\n",
    "        tmp = []\n",
    "        while(que):\n",
    "            node, depth = que.popleft()\n",
    "            if(depth > predepth):\n",
    "                result += calcTimes(tmp)\n",
    "                tmp = [node.val]\n",
    "                predepth = depth\n",
    "            else:\n",
    "                tmp.append(node.val)\n",
    "            if(node.left):\n",
    "                que.append([node.left, depth+1])\n",
    "            if(node.right):\n",
    "                que.append([node.right, depth+1])\n",
    "        result += calcTimes(tmp)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        if root is None:\n",
    "            return ans\n",
    "\n",
    "        levelmap = {}\n",
    "        level = 1\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            stack = []\n",
    "            while queue:\n",
    "                stack.append(queue.pop(0))\n",
    "            while stack:\n",
    "                node = stack.pop(0)\n",
    "                if level not in levelmap.keys():\n",
    "                    levelmap[level] = []\n",
    "                levelmap[level].append(node.val)\n",
    "                if node.left is not None:\n",
    "                    queue.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    queue.append(node.right)\n",
    "            # 计算当前层所需的操作次数\n",
    "            ans += f(levelmap[level])\n",
    "            level += 1\n",
    "        # 返回最终值\n",
    "        return ans\n",
    "\n",
    "# 抄自：https://leetcode.cn/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/solutions/1965827/python3-by-musing-clarkeeae-celd/\n",
    "def f(nums):\n",
    "    if not nums: return 0\n",
    "    v = {}\n",
    "    cnt = 0\n",
    "    for x, y in zip(nums, sorted(nums)):\n",
    "        # print(\"x={}, y={}, v={}\".format(x, y, v))\n",
    "        if x != y:\n",
    "            while x in v:\n",
    "                x = v[x]\n",
    "            if x != y:\n",
    "                cnt += 1\n",
    "                v[y] = x\n",
    "    return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self, n):\n",
    "        self.parents = {}\n",
    "        self.union_cnt = n\n",
    "    def find(self,x):\n",
    "        if(x != self.parents[x]):\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "    def union(self,x,y):\n",
    "        ax = self.find(x)\n",
    "        ay = self.find(y)\n",
    "        if(ax == ay):\n",
    "            return True\n",
    "        self.parents[ax] = ay\n",
    "        self.union_cnt -= 1\n",
    "        return False\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        que = deque()\n",
    "        que.append([root,1])\n",
    "        predepth = 0\n",
    "        def calcTimes(nums):\n",
    "            n = len(nums)\n",
    "            if(n <= 1):\n",
    "                return 0  \n",
    "            numsSort = sorted(nums)\n",
    "            us = UnionSet(n)\n",
    "            for num in nums:\n",
    "                us.parents[num] = num\n",
    "            for n1, n2 in zip(nums, numsSort):\n",
    "                us.union(n1,n2)\n",
    "            return n - us.union_cnt\n",
    "        result = 0\n",
    "        tmp = []\n",
    "        while(que):\n",
    "            node, depth = que.popleft()\n",
    "            if(depth > predepth):\n",
    "                result += calcTimes(tmp)\n",
    "                tmp = [node.val]\n",
    "                predepth = depth\n",
    "            else:\n",
    "                tmp.append(node.val)\n",
    "            if(node.left):\n",
    "                que.append([node.left, depth+1])\n",
    "            if(node.right):\n",
    "                que.append([node.right, depth+1])\n",
    "        result += calcTimes(tmp)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        queue = collections.deque([root])\n",
    "\n",
    "        # 置换环\n",
    "        def dp(ls):\n",
    "            cp = sorted(ls.copy())\n",
    "            mp = {nn:i for i, nn in enumerate(cp)}\n",
    "\n",
    "            res = []\n",
    "            for l in ls:\n",
    "                res.append(mp[l])\n",
    "\n",
    "            print('ls', ls)\n",
    "            print('cp', cp)\n",
    "            print('res', res)\n",
    "\n",
    "\n",
    "            vis = [False] * len(ls)\n",
    "            ans = 0\n",
    "            for i in range(len(res)):\n",
    "                idx = res[i]\n",
    "                if not vis[idx]:\n",
    "                    cnt = 0\n",
    "                    while not vis[idx]:\n",
    "                        vis[idx] = True\n",
    "                        idx = res[idx]\n",
    "                        cnt += 1\n",
    "                        # print('!!!')\n",
    "\n",
    "                    ans += cnt - 1\n",
    "            \n",
    "            return ans\n",
    "                \n",
    "\n",
    "\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            tmp = []\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "\n",
    "            ans += dp(tmp)\n",
    "        \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        q = [root]\n",
    "        ans = 0\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp, q = q, []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            \n",
    "            # 离散化\n",
    "            n = len(a)\n",
    "            b = sorted(range(n), key=lambda x:a[x])\n",
    "\n",
    "            # 操作数=长度-环数\n",
    "            ans += n \n",
    "            vis = [False] * n\n",
    "            for x in b:\n",
    "                if vis[x] : continue\n",
    "                while not vis[x]:\n",
    "                    vis[x] = True\n",
    "                    x = b[x]\n",
    "                ans -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        result = 0\n",
    "        q = [root]\n",
    "        qhead = 0\n",
    "        while (len(q) - qhead > 0):\n",
    "            size = len(q) - qhead\n",
    "            vals = []\n",
    "            for i in range(size):\n",
    "                node, qhead = q[qhead], qhead + 1\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                vals.append(node.val)\n",
    "            result += len(vals) - self.getLoops(vals)\n",
    "            \n",
    "        return result\n",
    "\n",
    "    def getLoops(self, arr):\n",
    "        loops = 0\n",
    "        \n",
    "        size = len(arr)\n",
    "        arr2 = [x for x in arr]\n",
    "        flag = [False for x in arr]\n",
    "        m = {}\n",
    "\n",
    "        arr2.sort()\n",
    "        for i in range(size):\n",
    "            m[arr2[i]] = i\n",
    "\n",
    "        for i in range(size):\n",
    "            if flag[i]:\n",
    "                continue\n",
    "            j = i\n",
    "            while not flag[j]:\n",
    "                k = m[arr[j]]\n",
    "                flag[j] = True\n",
    "                j = k\n",
    "            loops += 1\n",
    "\n",
    "        return loops\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        def count(Le):\n",
    "            c=0\n",
    "            L=list()\n",
    "            for i in Le:\n",
    "                L.append(i.val)\n",
    "            dic=dict()\n",
    "            l=L[:]\n",
    "            l.sort()\n",
    "            for i in range(len(L)):\n",
    "                dic[l[i]]=i\n",
    "            flag=[0]*len(L)\n",
    "            for i in range(len(L)):\n",
    "                if flag[i]==0:\n",
    "                    flag[i]=-1\n",
    "                    if dic[L[i]]==i:\n",
    "                        continue\n",
    "                    cn=0\n",
    "                    start=i\n",
    "                    now=dic[L[start]]\n",
    "                    while now!=start:\n",
    "                        cn+=1\n",
    "                        flag[now]=-1\n",
    "                        now=dic[L[now]]\n",
    "                    c+=cn\n",
    "            return c\n",
    "                                           \n",
    "        next=[root]\n",
    "        c=0\n",
    "        while next!=[]:\n",
    "            now=next\n",
    "            c+=count(now)\n",
    "            \n",
    "            next=[]\n",
    "            for i in now:\n",
    "                if i.left!=None :\n",
    "                    next.append(i.left)\n",
    "                if i.right!=None :\n",
    "                    next.append(i.right)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, q = 0, [root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def get(arr):\n",
    "    n = len(arr)\n",
    "    vis = [False]*n\n",
    "    ans = 0\n",
    "    for i in range(n):\n",
    "        if not vis[i]:\n",
    "            while not vis[i]:\n",
    "                vis[i] = True\n",
    "                ans += 1\n",
    "                i = arr[i]\n",
    "            ans -= 1\n",
    "    return ans\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        que = [root]\n",
    "        ans = 0\n",
    "        while que:\n",
    "            tem = []\n",
    "            for q in que:\n",
    "                if q.left: tem.append(q.left)\n",
    "                if q.right: tem.append(q.right)\n",
    "            #print([i.val for i in tem])\n",
    "            table = dict(zip(sorted(tem,key=lambda x:x.val),range(len(tem))))\n",
    "            tw = list(map(lambda x:table[x],tem))\n",
    "            ans += get(tw)\n",
    "            #print(tw)\n",
    "            que = tem\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        # 返回排序所需要最少交换次数，遍历数组内的置换环\n",
    "        def f(nums):\n",
    "            n = len(nums)\n",
    "            vis = [True]*n\n",
    "            nums = sorted(range(n), key = lambda i:nums[i])\n",
    "            res = 0\n",
    "\n",
    "            for i,x in enumerate(nums):\n",
    "                if not vis[i]: continue\n",
    "                vis[i] = False\n",
    "                while vis[x]:\n",
    "                    vis[x] = False\n",
    "                    x = nums[x]\n",
    "                    res+=1\n",
    "            return res\n",
    "        #bfs按层遍历\n",
    "        q = [root]\n",
    "        tq = []\n",
    "        res = 0\n",
    "        while len(q):\n",
    "            nums = []\n",
    "            while len(q):\n",
    "                r = q.pop(0)\n",
    "                nums.append(r.val)\n",
    "                if r.left: tq.append(r.left)\n",
    "                if r.right: tq.append(r.right)\n",
    "            res += f(nums)\n",
    "            q,tq = tq,q\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, q = 0, [root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        que = collections.deque([root])\n",
    "        while que:\n",
    "            s = len(que)\n",
    "            lst = []\n",
    "            while s > 0:\n",
    "                node = que.popleft()\n",
    "                lst.append(node.val)\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "                s -= 1\n",
    "            sorted_lst = sorted(lst)\n",
    "            d = {}\n",
    "            for i, x in enumerate(lst):\n",
    "                d[x] = i\n",
    "            for i in range(len(lst)):\n",
    "                if lst[i] != sorted_lst[i]:\n",
    "                    ans += 1\n",
    "                    index1, index2 = d[lst[i]], d[sorted_lst[i]]\n",
    "                    num1, num2 = lst[i], sorted_lst[i]\n",
    "                    lst[i], lst[d[sorted_lst[i]]] = lst[d[sorted_lst[i]]], lst[i]\n",
    "                    d[num1], d[num2] = index2, index1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        def resolve(orig: List[int]) -> int:\n",
    "            if len(orig) < 2:\n",
    "                return 0\n",
    "            opts = 0\n",
    "            s = {n:i for i,n in enumerate(sorted(orig))}\n",
    "            for i in range(len(orig)):\n",
    "                if s[orig[i]] == i:\n",
    "                    continue\n",
    "                while s[orig[i]] != i:\n",
    "                    j = s[orig[i]]\n",
    "                    orig[i], orig[j] = orig[j], orig[i]\n",
    "                    opts += 1\n",
    "            return opts\n",
    "        \n",
    "        if not root:\n",
    "            return 0\n",
    "        opts = 0\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            level = []\n",
    "            for i in range(len(q)):\n",
    "                n = q.popleft()\n",
    "                level.append(n.val)\n",
    "                if n.left:\n",
    "                    q.append(n.left)\n",
    "                if n.right:\n",
    "                    q.append(n.right)\n",
    "            opts += resolve(level)\n",
    "        return opts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, q = 0, [root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "\n",
    "            n = len(a)\n",
    "            a = sorted(range(n), key=lambda i: a[i])  # 离散化\n",
    "\n",
    "            ans += n\n",
    "            vis = [False] * n\n",
    "            for v in a:\n",
    "                if vis[v]: continue\n",
    "                while not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    v = a[v]\n",
    "                ans -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def f(self, nums:List[int]) -> int:\n",
    "        target = sorted(nums)\n",
    "        res = 0\n",
    "        map_ = dict()\n",
    "        for i in range(len(target)):\n",
    "            map_[target[i]] = i\n",
    "        for i in range(len(nums)):\n",
    "            while nums[i]!=target[i]:\n",
    "                index = map_[nums[i]]\n",
    "                temp = nums[i]\n",
    "                nums[i] = nums[index]\n",
    "                nums[index] = temp\n",
    "                res += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        cur = []\n",
    "        flag = root\n",
    "        res = 0\n",
    "        while queue:\n",
    "            p = queue.popleft()\n",
    "            cur.append(p.val)\n",
    "            if p.left:\n",
    "                queue.append(p.left)\n",
    "            if p.right:\n",
    "                queue.append(p.right)\n",
    "            if flag==p:\n",
    "                res += self.f(cur)\n",
    "                cur = []\n",
    "                if queue:\n",
    "                    flag=queue.pop()\n",
    "                    queue.append(flag)\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        # 返回排序所需要最少交换次数，遍历数组内的置换环\n",
    "        def f(nums):\n",
    "            n = len(nums)\n",
    "            vis = [True]*n\n",
    "            d = {}\n",
    "            res = 0\n",
    "            for i,x in enumerate(sorted(nums)):\n",
    "                d[x] = i\n",
    "            for i,x in enumerate(nums):\n",
    "                if not vis[i]: continue\n",
    "                y = x\n",
    "                vis[i] = False\n",
    "                while vis[d[y]]:\n",
    "                    vis[d[y]] = False\n",
    "                    y = nums[d[y]]\n",
    "                    res+=1\n",
    "            return res\n",
    "        #bfs按层遍历\n",
    "        q = [root]\n",
    "        tq = []\n",
    "        res = 0\n",
    "        while len(q):\n",
    "            nums = []\n",
    "            while len(q):\n",
    "                r = q.pop(0)\n",
    "                nums.append(r.val)\n",
    "                if r.left: tq.append(r.left)\n",
    "                if r.right: tq.append(r.right)\n",
    "            res += f(nums)\n",
    "            q,tq = tq,q\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        def f(nums):\n",
    "            n = len(nums)\n",
    "            vis = [True]*n\n",
    "            d = {}\n",
    "            res = 0\n",
    "            for i,x in enumerate(sorted(nums)):\n",
    "                d[x] = i\n",
    "            for i,x in enumerate(nums):\n",
    "                if not vis[i]: continue\n",
    "                y = x\n",
    "                vis[i] = False\n",
    "                while vis[d[y]]:\n",
    "                    vis[d[y]] = False\n",
    "                    y = nums[d[y]]\n",
    "                    res+=1\n",
    "            return res\n",
    "        q = [root]\n",
    "        tq = []\n",
    "        res = 0\n",
    "        while len(q):\n",
    "            nums = []\n",
    "            while len(q):\n",
    "                r = q.pop(0)\n",
    "                nums.append(r.val)\n",
    "                if r.left: tq.append(r.left)\n",
    "                if r.right: tq.append(r.right)\n",
    "            res += f(nums)\n",
    "            q,tq = tq,q\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        # bfs\n",
    "        l = [root]\n",
    "        ans = 0\n",
    "        while l:\n",
    "            new = []\n",
    "            for node in l:\n",
    "                if node.left:\n",
    "                    new.append(node.left)\n",
    "                if node.right:\n",
    "                    new.append(node.right)\n",
    "            l = new\n",
    "\n",
    "            n = len(l)\n",
    "            vals = [node.val for node in l]\n",
    "            # 离散化\n",
    "            vals = sorted(range(n), key=lambda i:vals[i])\n",
    "\n",
    "            # 置换环\n",
    "            not_vis = [True] * n\n",
    "            ans += n\n",
    "            for v in vals:\n",
    "                if not_vis[v]:\n",
    "                    ans -= 1\n",
    "                    while not_vis[v]:\n",
    "                        not_vis[v] = False\n",
    "                        v = vals[v]\n",
    "                    \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        # 返回排序所需要最少交换次数，遍历数组内的置换环\n",
    "        def f(nums):\n",
    "            \n",
    "            return res\n",
    "        #bfs按层遍历\n",
    "        q = [root]\n",
    "        tq = []\n",
    "        res = 0\n",
    "        while len(q):\n",
    "            nums = []\n",
    "            while len(q):\n",
    "                r = q.pop(0)\n",
    "                nums.append(r.val)\n",
    "                if r.left: tq.append(r.left)\n",
    "                if r.right: tq.append(r.right)\n",
    "\n",
    "            n = len(nums)\n",
    "            vis = [True]*n\n",
    "            nums = sorted(range(n), key = lambda i:nums[i])\n",
    "\n",
    "            for i,x in enumerate(nums):\n",
    "                if not vis[i]: continue\n",
    "                vis[i] = False\n",
    "                while vis[x]:\n",
    "                    vis[x] = False\n",
    "                    x = nums[x]\n",
    "                    res+=1\n",
    "            q,tq = tq,q\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        \"\"\"\n",
    "            保证没一层严格增序 \n",
    "                则需要保证left < right\n",
    "            \n",
    "            置换环  [2 0 1 4 3]  [2 0 1 ] [4 3]为两个置换环 \n",
    "        \"\"\"\n",
    "\n",
    "        ans,q = 0,[root]\n",
    "        while q:\n",
    "            a = []\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left : q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            n = len(a)\n",
    "            a = sorted(range(n),key=lambda i:a[i])\n",
    "\n",
    "            ans += n\n",
    "            vis = [False]*n\n",
    "            for v in a:\n",
    "                if vis[v]:continue\n",
    "                while not vis[v]:\n",
    "                    vis[v]= True\n",
    "                    v = a[v]\n",
    "                ans -=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ans,q=0,[root]\n",
    "        while q:\n",
    "            a=[]\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for node in tmp:\n",
    "                a.append(node.val)\n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "            n=len(a)\n",
    "            a=sorted(range(n),key=lambda i:a[i])\n",
    "            \n",
    "            ans+=n\n",
    "            vis=[False]*n\n",
    "            for v in a:\n",
    "                if vis[v]:continue\n",
    "                while not vis[v]:\n",
    "                    vis[v]=True\n",
    "                    v=a[v]\n",
    "                ans-=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        result = 0\n",
    "        q = [None for i in range(100001)]\n",
    "        qhead, qsize, size = 0, 0, 0\n",
    "        q[qsize], qsize = root, qsize + 1\n",
    "        while (qsize - qhead > 0):\n",
    "            size = qsize - qhead\n",
    "            vals = []\n",
    "            for i in range(size):\n",
    "                node, qhead = q[qhead], qhead + 1\n",
    "                if node.left:\n",
    "                    q[qsize], qsize = node.left, qsize + 1\n",
    "                if node.right:\n",
    "                    q[qsize], qsize = node.right, qsize + 1\n",
    "                vals.append(node.val)\n",
    "            result += len(vals) - self.getLoops(vals)\n",
    "            \n",
    "        return result\n",
    "\n",
    "    def getLoops(self, arr):\n",
    "        loops = 0\n",
    "        \n",
    "        size = len(arr)\n",
    "        arr2 = [x for x in arr]\n",
    "        flag = [False for x in arr]\n",
    "        m = {}\n",
    "\n",
    "        arr2.sort()\n",
    "        for i in range(size):\n",
    "            m[arr2[i]] = i\n",
    "\n",
    "        for i in range(size):\n",
    "            if flag[i]:\n",
    "                continue\n",
    "            j = i\n",
    "            while not flag[j]:\n",
    "                k = m[arr[j]]\n",
    "                flag[j] = True\n",
    "                j = k\n",
    "            loops += 1\n",
    "\n",
    "        return loops\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ret,q=0,deque([root])\n",
    "        while q:\n",
    "            # 需要逐层操作\n",
    "            sz=len(q)\n",
    "            level=[]\n",
    "            for i in range(sz):\n",
    "                cur=q.popleft()\n",
    "                level.append(cur.val)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            # 对当前着一层进行遍历，用cyclic sorting来查需要多少次swap，swap的次数是每个cyclic的长度-1\n",
    "            # 由于level中的数字未必是连续的，也未必是0-n，需要sort一下，不然的话只需要每个数字减去min(level)就可以了\n",
    "            temp=level.copy()\n",
    "            temp.sort()\n",
    "            mp={ele:idx for idx,ele in enumerate(temp)}\n",
    "            for i in range(len(level)):\n",
    "                while level[i]!=temp[i]:\n",
    "                    # 应该交换level[i]和另一个元素，让level[i]去他该去的地方\n",
    "                    should_go_to=mp[level[i]]\n",
    "                    level[i],level[should_go_to]=level[should_go_to],level[i]\n",
    "                    ret+=1\n",
    "        return ret\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        def num_swaps(a: list):\n",
    "            if not a:\n",
    "                return 0\n",
    "            num_pos = {num:i for i, num in enumerate(a)}\n",
    "            b = sorted(a)\n",
    "            i = 0\n",
    "            cnt = 0\n",
    "            while i < len(a):\n",
    "                if a[i] != b[i]:\n",
    "                    cnt += 1\n",
    "                    b_pos = num_pos[b[i]]\n",
    "                    a[b_pos] = a[i]\n",
    "                    num_pos[b[i]] = i\n",
    "                    num_pos[a[i]] = b_pos\n",
    "                    a[i] = b[i]\n",
    "                i += 1\n",
    "            return cnt\n",
    "        from collections import deque\n",
    "        root.layer = 0\n",
    "        layers = [[] for _ in range(10**5+10)]\n",
    "        d = deque([root])\n",
    "        while len(d):\n",
    "            node = d.popleft()\n",
    "            layers[node.layer].append(node.val)\n",
    "            if node.left:\n",
    "                node.left.layer = node.layer + 1\n",
    "                d.append(node.left)\n",
    "            if node.right:\n",
    "                node.right.layer = node.layer + 1\n",
    "                d.append(node.right)\n",
    "        ret = [num_swaps(_) for _ in layers]\n",
    "        return sum(ret)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ret,q=0,deque([root])\n",
    "        while q:\n",
    "            # 需要逐层操作\n",
    "            sz=len(q)\n",
    "            level=[]\n",
    "            for i in range(sz):\n",
    "                cur=q.popleft()\n",
    "                level.append(cur.val)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            # 对当前着一层进行遍历，用cyclic sorting来查需要多少次swap，swap的次数是每个cyclic的长度-1\n",
    "            # 由于level中的数字未必是连续的，也未必是0-n，需要sort一下，不然的话只需要每个数字减去min(level)就可以了\n",
    "            temp=level.copy()\n",
    "            temp.sort()\n",
    "            mp={ele:idx for idx,ele in enumerate(temp)}\n",
    "            for i in range(len(level)):\n",
    "                if level[i]!=-1 and level[i]!=temp[i]:\n",
    "                    \n",
    "                    # should_go_to[i]该去的位置\n",
    "                    should_go_to=mp[level[i]]\n",
    "                    # 表示遍历过了\n",
    "                    level[i]=-1\n",
    "                    chain_len=1\n",
    "                    while should_go_to!=i:\n",
    "                        # 把next加入环中\n",
    "                        chain_len+=1\n",
    "                        nval=level[should_go_to]\n",
    "                        level[should_go_to]=-1\n",
    "                        should_go_to=mp[nval]\n",
    "                        # should_go_to,level[should_go_to]=mp[level[should_go_to]],-1\n",
    "                    # 一个环已经遍历结束\n",
    "                    ret+=chain_len-1\n",
    "        return ret\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n",
    "        ret,q=0,deque([root])\n",
    "        while q:\n",
    "            # 需要逐层操作\n",
    "            sz=len(q)\n",
    "            level=[]\n",
    "            for i in range(sz):\n",
    "                cur=q.popleft()\n",
    "                level.append(cur.val)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            # 对当前着一层进行遍历，用cyclic sorting来查需要多少次swap，swap的次数是每个cyclic的长度-1\n",
    "            # 由于level中的数字未必是连续的，也未必是0-n，需要sort一下，不然的话只需要每个数字减去min(level)就可以了\n",
    "            temp=level.copy()\n",
    "            temp.sort()\n",
    "            mp={ele:idx for idx,ele in enumerate(temp)}\n",
    "            for i in range(len(level)):\n",
    "                print(f\"level[i]={level[i]},temp[i]={temp[i]}\")\n",
    "                if level[i]!=-1 and level[i]!=temp[i]:\n",
    "                    \n",
    "                    # next表示level[i]该去的位置\n",
    "                    ni=mp[level[i]]\n",
    "                    # 表示遍历过了\n",
    "                    level[i]=-1\n",
    "                    chain_len=1\n",
    "                    while ni!=i:\n",
    "                        # 把next加入环中\n",
    "                        chain_len+=1\n",
    "                        nval=level[ni]\n",
    "                        level[ni]=-1\n",
    "                        print(f\"{nval}\")\n",
    "                        ni=mp[nval]\n",
    "                    # 一个环已经遍历结束\n",
    "                    ret+=chain_len-1\n",
    "        return ret\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
